package q448_findDisappearedNumbers;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /*
    此题如果不需要考虑时间和空间复杂度则只需要排序后依次检查即可
    但是当需要只使用不额外的空间复杂度解决时：
    首先考虑如何将出现过的数字都标记起来 使得最后不会被统计
    这里的做法是 当我们遍历到一个数字时 我们将其对应位置的数字加上一个nums.length
    那么我们再次遍历的时候 如果有一个数字仍然处在 1 - n 之间 这就意味着这个位置没有因为出现过对应数字而加上数字
    那么这个位置就是我们需要统计的数
    需要注意的是 遍历时有可能出现已经被加过的数字 所以要取模处理

    当然 此题也可以使用负数的方式来标记对应位置的数字 仍然能够解决
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();

        for (int num : nums) {
            int x = (num - 1) % nums.length;
            nums[x] += nums.length;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= nums.length) res.add(i + 1);
        }

        return res;
    }
}
